package com.exercises;

import java.util.*;
import java.util.stream.Collectors;

class Exercise802 {
    public static void main(String[] args) {
        int[][] arr = new int[7][2];
        arr[0] = new int[]{1, 2};
        arr[1] = new int[]{2, 3};
        arr[2] = new int[]{5};
        arr[3] = new int[]{0};
        arr[4] = new int[]{5};
        arr[5] = new int[]{};
        arr[6] = new int[]{};
        System.out.println(new Exercise802().eventualSafeNodes(arr));
    }


    private int[] doList = null;

    public List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        doList = new int[n];
        for (int i = 0; i < n; i++) {
            dfs(graph, i);
        }
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (doList[i] == 2) result.add(i);
        }
        return result;
    }

    public boolean dfs(int[][] graph, int i) {
        if (doList[i] == 0) {
            doList[i] = 1;
            int[] dist = graph[i];
            boolean isSafe = true;
            for (int idx : dist) {
                isSafe = isSafe & dfs(graph, idx);
            }
            doList[i] = isSafe ? 2 : -1;
            return isSafe;
        }
        return doList[i] == 2;
    }
}
